﻿using System;
using System.Collections.Generic;

namespace DesignPattern.binaryHeap {
    public class MinHeap<T> where T : IComparable {
        public List<T> Data;

        public MinHeap(){
            Data = new List<T>();
        }

        public void Enqueue(T item){
            Data.Add(item);
            int child = Data.Count - 1;

            while (child > 0){
                int parent = (child - 1) / 2;

                if (Data[child].CompareTo(Data[parent]) >= 0)
                    break; // child item is larger than (or equal) parent so we're done

                Swap(ref Data, ref child, ref parent);
            }
        }

        public T Dequeue(){
            if (Data.Count == 0)
                throw new InvalidOperationException("Heap Empty");

            int last = Data.Count - 1;
            T first = Data[0];
            Data[0] = Data[last];
            Data.RemoveAt(last);
            int parent = 0;

            last--;

            while (true){
                int left = parent * 2 + 1; // Left child index of parent

                if (left > last)
                    break;

                int right = left + 1; // Right child index

                // If there is a right child, and it is smaller then the left child....
                if (right <= last && Data[right].CompareTo(Data[left]) < 0)
                    left = right;

                // If parent is <= to samllest child; done.
                if (Data[parent].CompareTo(Data[left]) <= 0)
                    break;

                Swap(ref Data, ref parent, ref left);
            }

            return first;
        }

        public T Peek(){
            if (Data.Count == 0)
                throw new InvalidOperationException("Heap Empty");

            return Data[0];
        }

        public void Clear(){
            Data.Clear();
        }

        public T[] ToArray(){
            return Data.ToArray();
        }

        public List<T> ToList(){
            return Data;
        }

        public int Count(){
            return Data.Count;
        }

        private void Swap(ref List<T> data, ref int x, ref int y){
            T temp = data[x];
            data[x] = data[y];
            data[y] = temp;
            x = y;
        }
    }
}